/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lenovo
 * Date: 2022-09-19
 * Time: 21:32
 */
public class HashBuck {
    //底层是数组+链表
    static class Node{
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    //数组容量
    Node[] arr ;
    public int usedsize;
    //负载因子
    public float DEFAULT_LOAD_FACTOR = 0.75f;

    public HashBuck() {
        this.arr = new Node[10];
        this.usedsize = usedsize;
    }
    /**
     * 根据key val增加
     */
    public void add(int key,int val){
        //1.将键值对转化为节点
        Node node = new Node(key,val);
        //2.检查数组里是否已经存在key值的节点
        int index = node.key%arr.length;
           //如果数组里不存在
           if (arr[index] == null){
               arr[index] = node;
           }else{
               //index已经存在,可能存在链表,需要遍历链表
               Node cur = arr[index];
               while (cur != null){
                   if(cur.key == node.key){//key在链表里已经存在,所以判断两个key的val
                       //如果val不同,则实现覆盖,然后返回
                       if(cur.val != node.val){
                           cur.val = node.val;
                           return;
                       }
                   }
                   cur = cur.next;
               }
              //代码走到这里,说明key在链表里一开始不存在,头插
                   node.next = arr[index];
                   arr[index] = node;
           }
        usedsize++;

           //判断负载因子
        if(loadFactor()>=DEFAULT_LOAD_FACTOR){
            //扩容
            grow();
        }
       }
    /**
     * 当前实际负载因子
     * @return
     */
    public float loadFactor(){
        return usedsize*1.0f/arr.length;
    }

    /**
     * 扩容函数
     */
    private void grow() {
        Node[] newArray = new Node[2*arr.length];
        //1.遍历数组每个元素的链表,数组的每个元素是链表的头结点
        //2.重新哈希
        //3.头插
        for (int i = 0; i < arr.length; i++) {
            Node cur = arr[i];//cur是每个链表的头结点
            //记录一下cur的next的值

            while(cur != null){ //遍历链表
                Node curNext = cur.next;
                //对cur节点重写hash
                int index = cur.key%newArray.length;
                //头插
                cur.next = newArray[index];
//                //这样写对吗?
//                cur = cur.next;
                newArray[index] = cur;
                cur = curNext;
            }

        }
        arr = newArray;
    }



    /**
     * 根据key返回value
     */
    public int get(int key){
        int index = key%arr.length;
        //key所在的位置没有元素
        if(arr[index] == null){
            return -1;
        }else{//key所在的位置有元素
            //可能是链表,因此要遍历这个链表
            Node cur = arr[index];
            while (cur != null){
                if(cur.key == key){//找到了
                    return cur.val;
                }
                cur = cur.next;
            }
            //循环里没有找到,因此代码走到这里,也没有找到
            return -1;
        }

    }
}
